There are many applications in medical imaging, science, and engineering for which there is a need to extract surface information from a three-dimensional field of values. In many applications it is desirable to visually represent information within three-dimensional fields of scalar values as isosurfaces. An isosurface, S, is a set of points on a scalar three-dimensional field having a constant value. That is, an isosurface S is a set of points for which f(x,y,z)=constant, where f(x,y,z) is a scalar three-dimensional function which is a function of coordinates x, y, and z. Such an isosurface is also sometimes called an implicit surface because the equation f(x,y,z)=constant defines an implicit function relating x, y, and z. As illustrative examples, the scalar three-dimensional function f(x,y,z) may be a mathematical formula or a scattered data array.
As illustrative examples of isosurfaces, an isosurface may represent a surface of constant pressure, temperature, velocity, or density. For example, in medical imaging isosurfaces are sometimes used to represent regions of constant density in a three-dimensional scan. Isosurfaces are important visualization tools in medical imaging, science visualization, and hydrodynamics. Isosurfaces also have many potential applications in three-dimensional graphics games and entertainment. As one example, metaballs are sometimes used to model fluids and also to generate special graphics effects. A metaball is defined by an implicit meatball function in which a threshold value defines a solid volume about a central point x0 y0 z0. For example, a meatball can be defined by an equation 1/((x−x0)2+(y−y0)2+(z−z0)2)=threshold. Metaballs are useful for representing soft, blobby objects that blend into each other. Metaballs can be visualized using isosurfaces.
A variety of algorithms have been developed to calculate polygonal mesh representations of isosurfaces using software algorithms executing on a central processing unit (CPU). These include techniques which work in a divide-and-conquer fashion in which groups of adjacent samples points associated with corners of a three-dimensional cell (or sub-cell) are tested to determine if the corner points lie inside or outside of a surface to be displayed. These include the marching cubes algorithm and the marching tetrahedral algorithm. The marching cubes algorithm is described in the article by Lorensen et al., “Marching Cubes”: A High Resolution 3D Surface Construction Algorithm,” Computer Graphics, 21 (4):163-169, July 1987, the contents of which are hereby incorporated by reference. The marching tetrahedron algorithm is a variation of the marching cubes algorithm using tetrahedrons instead of cubes and is described in various articles such as the article by Doi et al. “An Efficient Method of Triangulating Equivalued Surfaces by using Tetrahedral Cells,” IEICE Transcations Communication, Elec. Info. Syst, E74(1) 214-224, January 1991 and the article by Gueziec et al. “Exploiting Triangulated Surface Extraction using Tetrahedral Decomposition,” IEEE Transactions on Visualization and Computer Graphics, 1 (4) 328-342, December 1995, the contents of each of which are hereby incorporated by reference.
The marching cubes algorithm is a well-known method for scalar field polygonization. The marching cubes algorithm analyzes the scalar field along a sequence of cubes, where each cube has eight sample locations at the corners of the cube. The marching cubes algorithm determines at each corner of a cube whether the corner lies inside or outside of the isosurface. The marching cubes algorithm determines the polygon(s) required to represent the isosurface passing through the cube. Referring to FIG. 1, in the marching cubes algorithm a function f(x, y, z) is sampled on a cubic lattice. For each cubic cell, the marching cubes algorithm utilizes linear interpolation to estimate where the isosurface intersects cell edges. Tessellation is then performed depending upon the values of f(x,y,z) at the cell vertices to generate the polygon(s) of the isosurface passing through the cubic cell. The marching cubes algorithm has precalculated arrays supporting 256 different polygon configurations (i.e., with eight corners per cube, there are 28=256 possible corner configurations). That is for each cube cell there are 256 different ways for an isosurface to intersect the cell. However, the 256 different polygon configurations can be derived from 15 unique cases using operations such as reflections and rotations. FIG. 2 illustrates the 15 unique cube combinations for the marching cubes algorithm.
The marching tetrahedra algorithm is similar to the marching cube algorithm except that the sampling grid that has cubes decomposed into a tetrahedron mesh. A cube can be split several different ways into a set of tetrahedra. These include implementations in which five or six tetrahedera cover the volume of a cube. As illustrated in FIG. 3, the marching tetrahedra algorithm results in either one or two triangles per tetrahedral intersecting the isosurface.
As previously described, conventionally the marching cubes and marching tetrahedra algorithms are implemented on a CPU. As a result, in the prior art the polygonization of isosurfaces consumed substantial CPU resources. Moreover, the complex nature of marching cubes and marching tetrahedra computations make it difficult to optimize them for rapid execution on a CPU.
Therefore, in light of the above described problem, the apparatus, system, and method of the present invention was developed.